package com.java.comprehensive.arithmetic.leecode.tags.heap;

import java.util.Arrays;

/**
 * @Author: Dgg
 * @Date: 2021/12/29 21:35
 */
public class LeetCode_215 {


	public static int findKthLargest(int[] nums, int k) {
		if (nums.length <= 0) {
			return 0;
		}
		heapSort(nums);
		return nums[k - 1];
	}

	public static void heapify(int[] nums, int n, int i) {
		if (i >= n) {
			return;
		}
		int c1 = 2 * i + 1;
		int c2 = 2 * i + 2;
		int max = i;
		/** 边界(边界为小于nums的长度 不是下标) 和 值大小*/
		if (c1 < n && nums[c1] < nums[max]) {
			max = c1;
		}
		if (c2 < n && nums[c2] < nums[max]) {
			max = c2;
		}
		if (max != i) {
			swap(nums, max, i);
			heapify(nums, n, max);
		}
	}

	public static void buildHeap(int[] nums, int i) {
		int lastNode = i - 1;
		int parentNode = (lastNode - 1) / 2;
		for (int j = parentNode; j >= 0; j--) {
			heapify(nums, i, j);
		}
	}

	public static void swap(int[] nums, int i, int j) {
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}

	public static void heapSort(int[] nums) {
		buildHeap(nums, nums.length);
		for (int i = nums.length - 1; i >= 0; i--) {
			swap(nums, i, 0);
			heapify(nums, i, 0);
		}
	}

	public static void main(String[] args) {
		int[] nums = {3, 2, 1, 5, 6, 4};
		//1 2 3 5 6 4
		//4 2 3 5 6 1
		//
		buildHeap(nums, nums.length);
		System.out.println(Arrays.toString(nums));
	}
}
